1. Field of the Invention
This invention relates to the field of programmable logic devices and, more particularly, to the use of simulated annealing to optimize such devices.
2. Description of the Related Art
Simulated annealing is an optimization technique frequently used in the physical design of programmable logic devices (PLD's). As simulated annealing can be used to solve combinatorial optimization problems, the technique is commonly used to perform tasks such as partitioning, floorplanning, and placement for PLD's, and particularly field programmable gate arrays (FPGA's).
The technique explores multi-dimensional solution spaces to find an optimal solution through random generation of new combinatorial configurations. To generate a new configuration, an old or previous configuration is shuffled at random. For example, the configuration can be shuffled by displacing an object to a random location, exchanging locations of two or more objects, or performing other adjustments to the design that can affect a cost function. The cost function serves as a means of evaluating the quality of the proposed solution or move in view of predetermined design constraints.
Each configuration, such as a proposed FPGA placement solution, can be accepted or rejected based upon an evaluation of the cost function. If a decrease in the cost function occurs, the new configuration is accepted. Otherwise, the new configuration can be accepted with a probability that depends upon “temperature”.
As simulated annealing was inspired through an analogy with the cooling of metals, the iterative process is regulated by a cooling schedule that dictates temperature. The cooling schedule specifies an initial temperature, a final temperature, and a function for changing the temperature as the simulated annealing process continues. The decreasing temperature restricts the allowable moves in the annealing process as the temperature decreases. Accordingly, the exploration of different placement solutions is stressed at high temperatures, while the convergence to a particular solution is stressed at lower temperatures.
Though simulated annealing can provide high quality solutions for PLD designs, the process requires significant computational resources. To overcome this need, various techniques for reducing the amount of time and computing resources required have been proposed. These approaches have been classified into three general categories: controlled move generation strategies, parallel implementations of simulated annealing, and efficient annealing schedules.
With respect to move generation strategies, conventional simulated annealing techniques randomly shuffle the current placement configuration. Thus, during controlled move generation, each object has an equal likelihood of being selected for displacement. This probability can be expressed as: Pr(i)=1/N, where N is the total number of identical objects and
            ∑              i        =        1            N        ⁢                  ⁢          Pr      ⁡              (        i        )              =  1.The target location also is selected among all available locations with equal probability, at least within a range limited area. This probability can be expressed as: Pr(g,i)=1/N(g), where Pr(g,i) is the conditional probability of selecting a location i as a target and N(g) is the total number of selectable locations for group g.
The order in which moves are performed during simulated annealing is significant. Existing configurations are modified to produce new configurations. If the cost function decreases, the new configuration is accepted. The acceptance of a new configuration is an irreversible event in that subsequent configurations are based upon the most recently accepted configuration. Because of this, simulated annealing is said to be path dependent, meaning that the generation of a new configuration is conditionally dependent on the sequence of previously generated configurations.
As can be seen from the above discussion, conventional implementations of simulated annealing do not allow particular objects or target locations to be favored over others. This prevents knowledge that is specific to the circuit design, such as timing constraints and criticality, from being used in the simulated annealing process. It may be the case, for example, that some target locations will likely reduce propagation delays or reduce path criticality more so than others. These target locations, however, are not favored over others during conventional simulated annealing. In consequence, computer resources can be squandered in testing object moves and/or target locations that are unlikely to change the cost function and result in circuit optimization.
It would be beneficial to provide a technique for simulated annealing that encourages selection of objects and/or target locations for controlled move generation with respect to design considerations.